package SwordPointOffer.Tree;

import org.junit.Test;

import java.util.*;

class TreeNode {
  int val;
   TreeNode left;
  TreeNode right;
   TreeNode(int x) { val = x; }
}

class ListNode {
    int val;
     ListNode next;
    ListNode() {}
     ListNode(int val) { this.val = val; }
     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}
public class Tree {


    @Test
    public void reverse() {
        int x = -2147483648;
        String s = String.valueOf(x);
        char[] res = s.toCharArray();
        int flag;
        if(res[0]=='-')flag=-1;
        else flag = 1;
        StringBuilder reverResult = new StringBuilder();
        for(int i=res.length-1; i>=0; i--){
            if(res[i]!='-') reverResult.append(res[i]);
        }
        Long result = Long.valueOf(reverResult.toString()) * flag;
//        if(result>Integer.MAX_VALUE||result<Integer.MIN_VALUE)return 0;
        Integer r = Math.toIntExact(result);
//        System.out.println(IntegerResult);






    }

    @Test
    public void findContinuousSequence() {
        int target = 15;

        List<List<Integer>> res = new ArrayList<>();

        int p = 0;
        while (p < (target+1 ) / 2) {
            int temp = 0;
            List<Integer> list = new LinkedList<>();


            for (int i = p+1; i < target; i++) {
                temp = temp+i;
                if (temp  == target) {
                    list.add(i);
                    res.add(new ArrayList<>(list));
                    break;
                } else if (temp  > target) {
//                    System.out.println(list);
                    break;
                } else {
                    list.add(i);
                }
            }
            p++;
            System.out.println(p);


        }
        List<int[]> r = new ArrayList<>();
        for(int i=0;i<res.size();i++){
            int[] t = new int[res.get(i).size()];
            for(int j=0;j<res.get(i).size();j++){
                t[j]=res.get(i).get(j);
            }
        }
        System.out.println(res);

    }

    @Test
    public void minEatingSpeed() {
        int[] nums = {30,11,23,4,20};
        Map<Integer,Integer> map = new HashMap<>();
        for(int i=0;i<nums.length;i++){
            map.put(nums[i], map.getOrDefault(nums[i], 1)+1);
        }
        Set<Integer> set = map.keySet();
        for(int n:set){
            if(map.get(n)>(nums.length)/2) System.out.println(n);

        }

        int[] piles = {30,11,23,4,20};

        int h = 7;
        int len = piles.length;
        int k = 0, mean = 0, totalT = 0;
        Arrays.sort(piles);
//        System.out.println(piles[len]);
        if(len==h) System.out.println(piles[len - 1]);
        if(len>h) System.out.println(-1);
        if(len<h){
            int sum = Arrays.stream(piles).sum();

            if(sum%len!=0)mean = sum/h+1;
            else mean = sum/h;
            System.out.println(mean);
            for(int i=mean;i<piles[len-1];i++){
                for(int j=0;j<len;j++){
                    if((piles[j]/mean)<=0) {
                        totalT += 1;
                    }
                    else {
                        if(piles[j]%mean!=0)totalT += (piles[j]/mean+1);
                        else totalT += (piles[j]/mean);
                    }
                }

                if(totalT<=h) {
                    System.out.println("mean"+mean);
                    break;
                }
                mean++;
                totalT=0;
            }
        }
        System.out.println("end");
    }



    @Test
    public void computing() {
//        int m = (int)

        System.out.println();

    }

    @Test
    public void lengthOfLongestSubstring() {
        String s = "";
        if(s==" ") System.out.println(1);
        if(s.length()<1) System.out.println(0);
        int[] dp = new int[s.length()];
        Set<Character> set = new HashSet<>();
        for(int i=0;i<s.length();i++){
            int temp = 1;
            set.add(s.charAt(i));
            for(int j = i+1;j<s.length();j++){
                if(!set.add(s.charAt(j))==true){
                    set.clear();
                    break;
                }
                temp++;
                dp[i]=temp;
            }
            set.clear();

        }
        dp[s.length()-1]=1;

//        Arrays.sort(dp);
        String a = Arrays.toString(dp);
        System.out.println(a);

    }

    @Test
    public void findDuplicate() {
        int[] nums = {1};
        Set<Integer> set = new HashSet<>();
        for(int s:nums) {
            if (set.contains(s)) {
                s = s;
            } else {
                set.add(s);
            }
        }
        System.out.println(-1);
    }






    @Test
    public void LRUCache() {
        int capacity = 10;
        Map<String,Integer> map = new HashMap<>(capacity);
        Stack<Integer> stack = new Stack<>();

    }













    @org.junit.Test
    public void isPalindrome() {
        ListNode head = new ListNode(1);
        head.next = new ListNode(2);

        ListNode cp = copy(head);
//        System.out.println(cp.val);
        ListNode rev = reverse(head);
//        System.out.println(rev.val);
        while(rev!=null&&cp!=null){
            if(rev.val!=cp.val) System.out.println(false);

            rev=rev.next;
            cp=cp.next;
        }
        System.out.println(true);
    }
    ListNode reverse(ListNode node){
        ListNode cur = node;
        ListNode pre = null;
        while(cur!=null){
            ListNode nex = cur.next;
            cur.next= pre;
            pre=cur;
            cur = nex;
        }
        return pre;

    }
    ListNode copy(ListNode node){
        ListNode n = new ListNode(-1);
        ListNode cur = n;
        while(node!=null){
            ListNode nex = new ListNode(node.val);
            cur.next = nex;
            cur = cur.next;
            node = node.next;
        }
        System.out.println(n.next.val);
        cur.next = null;
        return n.next;

    }





    @org.junit.Test
    public void fib() {
//        if(n==0)return 0;
        int n = 4;
        // if(n==1)return 1;
        int[] dp = new int[n+1];
        dp[0]=0;
        dp[1]=1;
        for(int i=2; i<=n;i++){
            dp[i] = ( dp[i-1] + dp[i-2] )% 1000000007;;
        }
        System.out.println(dp[n]);
    }

    @org.junit.Test
    public void validPalindrome() {
        String s = "abc";
        if(judge(s)) System.out.println(true);

        StringBuilder res = new StringBuilder();
        int end = s.length();
        while(end >= 0){
            for (int i = 0; i < s.length(); i++) {
                if(i!=end){
                    res.append(s.charAt(i));
                }
            }
            if(judge(res.toString()))System.out.println(true);
            res.delete(0, res.length());
        }
        System.out.println("NO");
    }

    boolean judge(String s){
        for (int i = 0; i < s.length(); i++) {
            if(s.charAt(i)!=s.charAt(s.length()-i-1)){
                return false;
            }
        }
        return true;
    }


    @org.junit.Test
    public void mirrorTree() {
        String[] words = {"2", "1"};

        TreeNode root = new TreeNode(4);
        root.left = new TreeNode(2);
        root.right = new TreeNode(7);
        root.left.left  = new TreeNode(1);
        root.left.right = new TreeNode(3);
        root.right.left  = new TreeNode(6);
        root.right.right = new TreeNode(9);

        mirror(root);


    }

    private TreeNode mirror(TreeNode root) {
        if(root == null){
            return null;
        }
        TreeNode left = mirror(root.left);

        TreeNode right = mirror(root.right);

        root.left = right;
        root.right = left;

        return root;


    }


}
